Search for: All records

We investigate motion planning algorithms for the assembly of shapes in the tilt model in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules. We provide several heuristics and experimental evaluation of their success rate, solution length, and runtime. Video: https://youtu.be/VU1SZYzeaXw Transcript: This animation shows colored tiles moved by a global signal so they all move in the same direction unless blocked. This simple example is solved using the Greatest Distance heuristic, which finds the shortest path in 21 steps. Each tile has glue on the four sides that only stick to compatible glues. Glue type is denoted by color. The objective is to manipulate the tiles to bond in the shape of the connected polyomino target outlined in red. The Polyomino Assembly Problem is PSPACE-hard, so optimal solutions are difficult to find. This more complicated workspace was solved using the Minimum Move to Polyomino or Target. This approach is not optimal, but is a best-first search that attempts to keep tiles not involved in the present construction step separated from each other. This is done by pruning configurations with undesired subassemblies from the search tree. The solution requires 473 steps.